package com.learn.algorithm_74;

/**
 * 74. 搜索二维矩阵
 *
 * https://leetcode-cn.com/problems/search-a-2d-matrix/solution/sou-suo-er-wei-ju-zhen-by-leetcode/
 *
 * @author gatts, 2020/8/26 18:00
 */
public class Search2dMatrix {

    public static void main(String[] args) {
        new Search2dMatrix().process();
    }

    /**
      输入:
         matrix = [
         [1,   3,  5,  7],
         [10, 11, 16, 20],
         [23, 30, 34, 50]
         ]
         target = 3
      输出: true
     */
    public void process(){
        int[][] matrix = new int[][]{
                {1,   3,  5,  7},
                {10, 11, 16, 20},
                {23, 30, 34, 50}
        };
        int target = 3;

        searchMatrix(matrix, target);
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if (m == 0) return false;
        int n = matrix[0].length;

        // 二分查找
        int left = 0, right = m * n - 1;
        int pivotIdx, pivotElement;
        while (left <= right) {
            pivotIdx = (left + right) / 2;
            pivotElement = matrix[pivotIdx / n][pivotIdx % n];
            System.out.println(String.format("pivotIdx: %d, pivotElement: %d", pivotIdx, pivotElement));
            if (target == pivotElement) return true;
            else {
                if (target < pivotElement) right = pivotIdx - 1;
                else left = pivotIdx + 1;
            }
        }
        return false;
    }

}
